#include <iostream>
#include <boost/foreach.hpp>
#define feach BOOST_FOREACH

#include <cstdlib>
#include <cstring>
#include <time.h>
#include <cmath>

#include "structs.hh"
#include "greedy.hh"

using namespace std;

BTS** BestSolution;
uint maxIncome = 0;

static bool findInArray ( BTS** BTSArray, BTS* value ) {
  uint i = 0;
  while ( BTSArray[i] != NULL ) 
    if ( BTSArray[i++] == value ) return true;

  return false;
}

/**
 * Cette fonction calcul les revenus générés par la completion de la solution
 * partielle grâce à l'algorithme glouton déterministe pouvant fractionner les
 * objets.
 *
 * @param d Le jeux de donnée.
 * @param currentSolution Solution à compléter.
 *
 * @return Les revenus générés par la solution complétée.
 */
static uint overEstimate ( 
    Dataset d,
    BTS** currentSolution ) {
  uint incomes = 0;
  uint subscribers = 0;

  uint offset = 0; 
  while ( currentSolution[offset] != NULL ) {
    incomes += currentSolution[offset]->incomes;
    subscribers += currentSolution[offset++]->subscribers;
  }

  uint i = 0;
  while ( subscribers < d.capacity && i < d.numberOfBTS ) {
    if ( !findInArray ( currentSolution, d.stations + i ) ) {
      double f = 1.0;
      if ( d.stations[i].subscribers + subscribers > d.capacity )
        f = (double)(d.capacity - subscribers) / 
          (double)(d.stations[i].subscribers);

      subscribers += ceil ( f * (double)d.stations[i].subscribers );
      incomes += ceil ( f * (double)d.stations[i].incomes );
    }
    ++i;
  }

  return incomes;
}

/**
 * Fonction d'acceptation des solutions. Cette fonction vérifie d'une part que
 * la solution proposée ne viole pas les contraintes du problème (ici le nombre 
 * d'abonnées) et d'autre part que la solution est prometteuse.
 *
 * @param d Le jeux de donnée.
 * @param solution La solution à vérifier.
 *
 * @return true si la solution est valable. false sinon.
 */
static bool accept ( Dataset d, BTS** solution ) {
  uint incomes = 0; uint subscribers = 0; uint i = 0;
  while ( solution[i] != NULL ) {
    subscribers += solution[i]->subscribers;
    incomes += solution[i++]->incomes;
  }

  if ( subscribers <= d.capacity 
      && overEstimate ( d, solution ) >= maxIncome ) {
    if ( incomes >= maxIncome ) {
      memcpy ( BestSolution, solution, d.numberOfBTS * sizeof(BTS*));
      maxIncome = incomes;
    }
    return true;
  }

  return false;
}

/** 
 * Algorithme de Backtracking dont la fonction accept à 
 * été modifiée afin de vérifier que le sous-arbre est prometteur
 *
 * @param d Le jeux de données.
 * @param subscribers Le nombre courant d'abonnés.
 * @param recLevel Niveau de récursion.
 * @param startStation Station à partir de laquelle la recherche doit continuer.
 * @param solution Solution courante à compléter (éventuellement).
 */
void branchAndBound ( 
    Dataset d,
    uint subscribers,
    uint recLevel,
    uint startStation,
    BTS** solution ) {

  checkTime ();

  if ( !accept ( d, solution ) ) {
    solution [recLevel - 1] = NULL;
    return ;
  }

  for ( uint i = startStation; i < d.numberOfBTS; ++i ) {
    solution[recLevel] = d.stations + i;
    branchAndBound ( d, subscribers + d.stations[i].subscribers, 
        recLevel + 1, i + 1, solution );
  }

  if (recLevel != 0 ) solution [recLevel - 1] = NULL;
}

int main ( int argc, char** argv ) {
  if ( argc != 2 ) return 0;

  srand ( time(NULL) );
  Dataset d = readDataSet ( string(argv[1]) );

  BestSolution = new BTS*[d.numberOfBTS + 1];
  BTS** solutionSpace = new BTS*[d.numberOfBTS + 1];
  for ( uint i = 0; i < d.numberOfBTS + 1; ++i )
    BestSolution[i] = solutionSpace[i] = NULL;

  qsort ( d.stations, d.numberOfBTS, sizeof(BTS), BTS_Cmp ); 

  startTimer();
  vector < BTS* > greedySolution = greedy ( d );
  for ( uint i = 0; i < greedySolution.size(); ++i )
    maxIncome += greedySolution[i]->incomes;

#ifndef BENCHMARK
  cout << "Estimation greedy : " << maxIncome << endl;
#endif

  branchAndBound ( d, 0, 0, 0, solutionSpace);
  stopTimer();

#ifndef BENCHMARK
  displaySolution ( d, BestSolution );
#endif
  return 0;
}
